package LeetCode;

import java.util.HashSet;
import java.util.Set;

public class LC_421_MaximumXORofTwoNumbersinanArray {

    public static void main(String[] args) {

    }

    static class Solution {
        public int findMaximumXOR(int[] nums) {
            int max = 0, mask = 0;
            for (int i = 31; i >= 0; i--) {
                mask = mask | (1 << i);
                Set<Integer> set = new HashSet<>();
                for (int num : nums)
                    set.add(num & mask);
                int tmp = max | (1 << i);
                for (Integer prefix : set) {
                    if (set.contains(prefix ^ tmp)) {
                        max = tmp;
                        break;
                    }
                }
            }
            return max;
        }

    }

    public class Solution_1 {

        class Trie {
            Trie[] next;

            Trie() {
                next = new Trie[2];
            }
        }

        public int findMaximumXOR(int[] nums) {
            if (nums.length <= 1)
                return 0;
            Trie root = new Trie();
            int result = 0;
            for (int num : nums) {
                int xor = 0;
                Trie insert = root, search = root;
                for (int i = 30; i >= 0; i--) {
                    int bit = (num >>> i) & 1;
                    int rbit = bit ^ 1;
                    if (insert.next[bit] == null) {
                        insert.next[bit] = new Trie();
                    }
                    insert = insert.next[bit];
                    if (search != null) {
                        if (search.next[rbit] != null) {
                            xor += (1 << i);
                            search = search.next[rbit];
                        } else {
                            search = search.next[bit];
                        }
                    }
                }
                result = Math.max(result, xor);
            }
            return result;
        }

    }
}